class _Node<T> {
  value: T
  next: _Node<T> | undefined
  constructor(value: T) {
    this.value = value
    this.next = undefined
  }
}

/**
 *
 * @description 如果你在大型数组上做了很多 Array#push() 事情 Array#shift() ，你应该使用这个包而不是数组，因为 Array#shift() 具有线性时间复杂度 O（n），而 Queue#dequeue() 具有恒定的时间复杂度 O（1）。这对大型阵列来说有很大的不同
 * 参考： https://github.com/sindresorhus/yocto-queue | https://juejin.cn/post/7175079506326077477 | https://juejin.cn/post/7116333717152333861 (详细)
 *
 *
 * 在 Queue 中，创建 head 和 tail 头尾指针，并定义 size 来记录大小。每次遍历的时候先找到头结点，然后通过每个结点的 next 指针往后走。这样一看是不是又很像链表。
 *
 * head 指向头节点，用于模拟 shift 来删除第一个元素；tail 指向尾节点，用于模拟 push 向末尾添加新元素
 *
 * 先进先出
 */
class yoctoQueue<ValueType> implements Iterable<ValueType> {
  /**
   * 头指针
   */
  $head: _Node<ValueType> | undefined
  /**
   * 尾指针
   */
  $tail: _Node<ValueType> | undefined
  /**
   * 记录大小
   */
  $size!: number
  constructor() {
    this.clear()
  }

  /**
   * 尾指针入队
   */
  enqueue(value: ValueType): void {
    const node = new _Node(value)
    if (this.$head) {
      this.$tail!.next = node // 这个要先设置，因为这个引用也在头部指针上
      this.$tail = node
    } else {
      this.$head = node
      this.$tail = node
    }
    this.$size++
  }

  /**
   * 头指针出队
   */
  dequeue(): ValueType | undefined {
    const current = this.$head
    if (!current) return

    this.$head = current.next
    this.$size--
    return current.value
  }

  /**
   * 获取头指针的内容
   */
  peek(): ValueType | undefined {
    if (!this.$head) {
      return
    }
    return this.$head.value
  }

  *[Symbol.iterator](): IterableIterator<ValueType> {
    let current = this.$head
    while (current) {
      // 将所有的元素都遍历一遍，用yield返回所需要的，从而形成迭代（for of自动调用generator函数的next方法也就是这里yield所返回的值）
      yield current.value
      current = current.next
    }
  }

  get size(): number {
    return this.$size
  }
  clear(): void {
    this.$head = undefined
    this.$tail = undefined
    this.$size = 0
  }
}

export default yoctoQueue
